/**
 * 对于一个满二叉树，已知他的先序遍历
 * 求他的后续遍历
 * 
 * 对于一般的二叉树，仅根据先序或者后序，无法确定另一个的遍历顺序。但是对于满二叉树，任意一个
 * 节点的左右子树都含有相同的节点，同时先序遍历的第一个节点作为后续遍历的最后一个节点
 * 由此得到pre->post的递归模型
 * 当pre的左指针比右指针靠右，则不操作
 * 否则
 * 取中间位置 这里可以取中间位置是因为这是一个完全二叉树
 * 将pre的左半部分（不包括第一个）转换为post的左半部分
 * 将pre的右半部分转换为post的右半部分
 * 
 * 其中post[right2] = pre[left1]表示后序遍历的最后一个节点（根节点）等于先序遍历的第一个节点（根节点）
 */

/**
 * 两个遍历数组
 * 开始下标和结束下标
 */
void pre2post(int pre[],int left1,int right1,int post[],int left2,int right2){
    int half;
    if(right1>=left1){//对pre不断转换
        post[right2]=pre[left1];//post
        half=(right1-left1)/2;
        pre2post(pre,left1+1,left1+half,post,left2,left2+half-1);
        pre2post(pre,left1+half+1,right1,post,left2+half,right2-1);
    }

}